Batch 2 - Class 285 - Lights out

• There are balls of 10 different colors. All balls are of 10gm each, except one color which are all either 9gm or 11gm (we do not know for sure). There is a weighing scale where we can put any number of balls and read the weight. In one weighing, figure out which balls are odd weight, and whether they are lighter of heavier than others.
• Answer: Take 1 ball of 1st color, 2 balls of 2nd color, and so on. Weigh the 55 balls. The difference of weight from 550gm is the pile from which those balls were taken. The weight being more or less than 550 denotes heavier or lighter balls resp.

• What if we knew that exactly two stacks were defective (in the same way)?
• Answer: We can map the possibilities - we land up with the Fibonacci sequence
• What if any number of stacks could be defective?
• Answer: We can map the possibilities - we land up with powers of 2. Note that this is a generalized solution, so subsumes the previous two problems as well

• There is a grid (lets say 3x3) of lights. Some of the lights are initially ON. Whenever you press a light, that lights and its (upto) four adjacent lights toggle. Can you switch off all the lights through this process? Example is shown below

• How many times may you have to press a light? What happens if you press the same switch twice?
• Does the order of pressing switches matter?
• It is same as not pressing it at all.
• Can you figure out all the combinations?
• You only have nine possible actions in the whole game, and you have to just pick a combination (not a permutation)
• Older kids who have done this may think of this in terms of system of linear equations
• How do you think about (a) solvability, (b) uniqueness of solution once you start to think of this as a system of linear equations?
• Answer: If there are nine variables, one standing for each cell, and that variable can have a value of 1 or 0, then each influences certain lights. This gives us 9 simultaneous linear equations to solve. In this case, those are non-dependent, and hence there is exactly one solution to every starting point. Note that the starting points form the right hand side of these simultaneous linear equations. Note that you are solving the equations mod 2.
• Answer:

• Take another of these problems and let kids solve it

• Are all patterns on all grids solvable?
• Lets try a smaller 3x2 grid. Is that always solvable?
• Try to go from all ON to all OFF
• Try to go from any one ON to all OFF
• Lets try to look at this procedurally/ programatically - how would you list all possible solvable patterns on a given grid?
• Solvable means you can get from there to all OFF
• So what can be our starting point to find all solvable patterns?
• And now we only need to cycle through all binary combinations of switches. So its going to take time, but we can get this done.
• Any smarter alternative?
• We could keep a record of all potential configurations, and initial marked them as unsolved. Then we take a solved position, like all OFF, and look at all its next possibilities - mark them solved. Keep doing this, till we go through a complete iteration of going through and not marking any new position.
• So here's the 3x2 positions that are solvable

• Actually, there may be multiple solutions here - can you find multiple solutions to go from all ON to all OFF (kids may have already done this as part of earlier exercise)

• The real lights out game is played on a 5x5 grid
• Is this always solvable? No, it happens that it is solvable in one-fourth of the starting point configurations! Kids who are interested in theory behind it may refer to https://www.jaapsch.net/puzzles/lomath.htm
• If you take a random pattern, there is an interesting way to solve it (if a solution exists). Its called Light Chasing
• Number the rows 1-5, the columns A-E.
• (a) For each light on row 1, press the button beneath it on row 2 to turn the light off. This way row 1 is completely unlit.
• (b) Repeat step a for rows 2-4, so that now you only have lights on row 5. This is usually called 'chasing the lights'.
• (c) If the light at A5 is on, press D1 and E1. 
•      If the light at B5 is on, press B1 and E1.      
•      If the light at C5 is on, press D1.
• (d) Repeat steps a-b, chasing the lights down and it will be magically solved.
• This method will not solve the puzzle in the shortest possible way, but it is very simple
• It doesnt solve all cases, for example one with A1, A2, A4 and A5 on - this is solvable but not with the chaser
• Lets try this at https://www.jaapsch.net/puzzles/javascript/lightjvr.htm

• Find the right angled triangle with the largest perimeter, with one of the sides measuring 13 units